<?php
/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2019/3/19
 * Time: 23:16
 */
/*
 * 冒泡排序算法:
 * 对需要排序的数组从后往前（逆序）进行多遍的扫描，当发现相邻的两个数值的次序与排序要求的规则不一致时，
 * 就将这两个数值进行交换。这样比较小（大）的数值就将逐渐从后面向前面移动
 * */
function bubbleSort($arr)
{
    for ($i = 0; $i < count($arr); $i++) {
        $isSort = false;
        for ($j = 0; $j < count($arr) - $i - 1; $j++) {
            if ($arr[$j] < $arr[$j + 1]) {
                $isSort = true;
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
        if ($isSort) {
            break;
        }
    }
    return $arr;
}

//$arr = array(3,1,2);
//var_dump(bubbleSort($arr));

/*
 * 快速排序：
 * 在数组中挑出一个元素（多为第一个）作为标尺，扫描一遍数组将比标尺小的元素排在标尺之前，
 * 将所有比标尺大的元素排在标尺之后，通过递归将各子序列分别划分为更小的序列直到所有的序列顺序一致
 * */
function quickSort($arr)
{
    //先判断是否需要继续进行
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }

    $base_num = $arr[0];//选择一个标尺 选择第一个元素

    //初始化两个数组
    $left_array = array();//小于标尺的
    $right_array = array();//大于标尺的
    for ($i = 1; $i < $length; $i++) {      //遍历 除了标尺外的所有元素，按照大小关系放入两个数组内
        if ($base_num > $arr[$i]) {
            //放入左边数组
            $left_array[] = $arr[$i];
        } else {
            //放入右边
            $right_array[] = $arr[$i];
        }
    }
    //再分别对 左边 和 右边的数组进行相同的排序处理方式
    //递归调用这个函数,并记录结果
    $left_array = quickSort($left_array);
    $right_array = quickSort($right_array);
    //合并左边 标尺 右边
    return array_merge($left_array, array($base_num), $right_array);
}

//$arr = array(3,1,2);
//var_dump(quickSort($arr));

/*
 * 二分查找：
 * 假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；
 * 若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
 * */
function binarySearch(Array $arr, $target)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        #找到元素
        if ($arr[$mid] == $target) return $mid;
        #中元素比目标大,查找左部
        if ($arr[$mid] > $target) $high = $mid - 1;
        #重元素比目标小,查找右部
        if ($arr[$mid] < $target) $low = $mid + 1;
    }

    #查找失败
    return false;
}